SPOJ/NHAY - 32. A Needle in the Haystack/nhay.cpp

   1 using namespace std;
   2 #include <cstdio>
   3 #include <cstring>
   4 #include <iostream>
   5 #include <vector>
   6 #include <string>
   7 #include <cassert>
   8
   9 const int MAXN = 1000010;
  10
  11 vector<int> border;
  12
  13 void preocomputeBorder(const string &needle) {
  14     int m = needle.size();
  15     border.resize(m + 1);
  16     border[0] = -1;
  17     for (int i = 0; i < m; ++i) {
  18       border[i+1] = border[i];
  19       while (border[i+1] > -1 and needle[border[i+1]] != needle[i]) {
  20         border[i+1] = border[border[i+1]];
  21       }
  22       border[i+1]++;
  23     }
  24     for (int i = 0; i <= m; ++i) {
  25         printf("%d ", border[i]);
  26     }
  27     puts("");
  28 }
  29
  30 int main(){
  31     int m;
  32     while (scanf("%d", &m) == 1) {
  33         string needle; getline(cin, needle);
  34         getline(cin, needle);
  35         preocomputeBorder(needle);
  36
  37         int seen = 0;
  38
  39         for (int i = 0; ; ++i) {
  40             char c = getchar();
  41             if (c == '\n' or c == EOF) break;
  42             assert(c != EOF);
  43             //cout << c << endl;
  44
  45             while (seen > -1 and needle[seen] != c) {
  46                 seen = border[seen];
  47             }
  48             if (++seen == m) {
  49                 printf("%d\n", i - m + 1);
  50                 seen = border[m]; // There are no more characters in needle, so with the next input character let's try with the border of the whole needle.
  51             }
  52         }
  53         puts("");
  54     }
  55     return 0;
  56 }